﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

public class Solution128
{
    //空间换时间
    public int LongestConsecutive(int[] nums)
    {//第一次遍历，所有的存哈希表

        int len=nums.Length;

        int maxLen = 0;
        HashSet<int> map = new HashSet<int>();

        for (int i = 0; i < len; i++)
        {

            map.Add(nums[i]);
        }
        for (int i = 0; i < len; i++)
        {

            int cur = nums[i];
            int pre = nums[i]-1;
            //cur必须是起点,也就是没有先驱结点，否则时间复杂度就是n2了
            //这样每个子序列是遍历一次
            if (!map.Contains(pre))
            {
                //检查这个子序列的长度
                int curLen = 0;
                while (map.Contains(cur)) {

                    curLen++;
                    cur= cur+1;
               

                }
                maxLen=Math.Max(maxLen, curLen);    

            }
        }

        return maxLen;
    }
}

class Program128
{

    static void Main128(string[] args)
    {
        Solution128 solution = new Solution128();
        int[] nums = [100, 4, 200, 1, 3, 2];


     int res=   solution.LongestConsecutive(nums);
        Console.WriteLine(res);


    }
}